package unit13_动态规划.part3_大厂冲刺题;

public class LongestPalindrome {




    public int longestPalindrome(String ss) {
        char[] s = ss.toCharArray();
        int n = s.length;
        if (n == 0) {
            return 0;
        }

        int[][] f = new int[n][n];
        int i, j=0;
        for (i = 0; i < n; i++) {
            f[i][j] = 1;
        }

        for (i = 0; i < n - 1; i++) {
            f[i][i + 1] = (s[i] == s[i + 1]) ? 2 : 1;
        }
        for (int len = 3; len <= n; len++) {
            for (i = 0; i <= n - len; i++) {
                j = i + len - 1;
                f[i][j] = Math.max(f[i][j - 1], f[i + 1][j]);
                if (s[i] == s[j]) {
                    f[i][j] = Math.max(f[i][j], f[i + 1][j - 1] + 2);
                }
            }
        }
        return f[0][n - 1];
    }
}
